﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution72
{
    public int MinDistance(string word1, string word2)
    {
        int m = word1.Length;
        int n = word2.Length;

        int[][] dp = new int[m + 1][];//以这个字符结尾的，是不是子序列

        for (int i = 0; i <= m; i++)
        {


            dp[i] = new int[n + 1];
            dp[i][0] = i;//word=i,变word=0,需要操作i次，删除
        }
        for (int i = 0; i <= n; i++)
        {


           
            dp[0][i] = i;//word=i,变word=0,需要操作i次，删除
        }

        //两种操作,插入和替换
        for (int i = 1; i <= m; i++)
        {


            for (int j = 1; j <= n; j++)
            {


                //从长度少一个的转移过来，肯定要操作一次

                dp[i][j] = Math.Min(  dp[i ][j - 1]+1, dp[i-1][j]+1);


                if (word1[i - 1] == word2[j - 1])
                {
                    Console.WriteLine(dp[i][j]);
                    dp[i][j] = Math.Min(dp[i][j], dp[i - 1][j - 1]); //相同不需要操作

                }
                else
                {



                    dp[i][j] = Math.Min(dp[i][j], dp[i - 1][j - 1]+1);//不同同替换一次

                }


            }
        }

        return dp[m][n];
    }
}
